Computers interface to one or more storage devices that incorporate removable or non-removable storage media. Examples of storage media include floppy disks, hard disks, CD ROMs, digital versatile disks (DVD) and the like. The storage media is used to store various types of information. For example, when a user creates a document with a word processing application program, the document can be saved as data on the storage media. A request is sent from the application program to an operating system executing in the computer. The operating system in turn sends a request to the storage device to store the data. The storage device then stores the data as part of a file on the storage media. The user can then later retrieve the data via the operating system, further manipulate the document, and resave the data as needed.
Data for the file is stored onto individual units on the storage media referred to as blocks or clusters. The storage media is organized so that the operating system can locate unallocated blocks (without stored data), to store new data and so that the operating system can locate and retrieve the data for the file. Thus, each file typically includes not only the data to be stored but also certain control information. For example, the control information identifies blocks on the storage media that include data for the file. The storage media also includes a free space map identifying blocks on the storage media that include stored data, i.e. allocated blocks; and blocks that are available to store new data, i.e. unallocated blocks.
To properly create a file, the operating system completes a series of transactions. The operating system reads the free space map to identify unallocated blocks on the storage media that can be used to store the data for the file. After a sufficient number of unallocated blocks are identified, the operating system sends a request to the storage device to store the data to the identified unallocated blocks. The operating system also updates the free space map on the storage media so that the blocks containing the file data are identified as allocated.
If the operating system fails to complete one or more of the transactions, the integrity of the storage media can become corrupted. Specifically, an inconsistency may occur between the free space map and the control information associated with one or more of the files on the storage media. For example, the operating system sends a request to the storage device to store the data associated with a first file along with its control information. However, the computer may crash or be shut off before the operating system updates the free space map. As a result, the free space map identifies one or more blocks, which include data for the first file, as unallocated. During a subsequent write operation for a second file, one or more of the blocks that include data for the first file are allocated to the second file because the blocks are identified in the free space map as unallocated. A loss of data can then occur when the data for the second file is stored on blocks allocated to both the first file and the second file. When one or more blocks are allocated to two or more files, the files are said to be “cross-linked.”
The methods presently available to detect and correct cross-linked files are slow and inefficient. In known systems, a utility reads the data storage control information for all of the files on a storage media to identify cross-linked files. The amount of time required to read the control information for all of the files on the storage media can be on the order of many minutes or even hours depending on the media type, size and also the device speed. Data on the storage media cannot, for example, be accessed by other applications while the utility is executing. Because the storage media cannot be accessed while the utility is running, the methods presently available provide an inconvenient means to detect and correct cross-linked files.